package com.Sep_Sixteen;

import java.util.ArrayList;
import java.util.List;

/**
 * 501. 二叉搜索树中的众数
 * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
 *
 * 如果树中有不止一个众数，可以按 任意顺序 返回。
 *
 * 假定 BST 满足如下定义：
 *
 * 结点左子树中所含节点的值 小于等于 当前节点的值
 * 结点右子树中所含节点的值 大于等于 当前节点的值
 * 左子树和右子树都是二叉搜索树
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Solution501 {

    private int maxCount;
    private int count;
    private TreeNode pre;
    List<Integer> list;

    public int[] findMode(TreeNode root) {
        list=new ArrayList<>();
        maxCount=0;
        count=0;
        pre=null;
        findMode1(root);
        int[] ans=new int[list.size()];
        for(int i=0;i<list.size();i++)
        {
            ans[i]=list.get(i);
        }
        return ans;
    }

    public void findMode1(TreeNode root){
        if (root==null) return;
        findMode1(root.left);
        int rootVal=root.val;
        if (pre==null||rootVal!= pre.val)
        {
            count=1;
        }else
        {
            count++;
        }
        if (count>maxCount)
        {
            list.clear();
            list.add(rootVal);
            maxCount=count;
        }else if (count==maxCount)
        {
            list.add(rootVal);
        }
        pre=root;
        findMode1(root.right);

    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
